/**
 * 1st, filter out all the available digits.
 * 
 * 2nd, using BFS to compose every possible digits, 
 * check the number when it's the multiple of the given N;
 */

/**
 * @author antonio081014
 * @since Nov 17, 2011, 8:16:26 AM
 */
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class MultiplesWithLimit {
	public List<String> nonForbidden;
	public boolean[] visited;

	public String minMultiples(int N, int[] forbiddenDigits) {
		nonForbidden = new ArrayList<String>();
		for (int i = 0; i <= 9; i++) {
			boolean flag = true;
			for (int j = 0; j < forbiddenDigits.length && flag; j++) {
				if (i == forbiddenDigits[j])
					flag = false;
			}
			if (flag)
				nonForbidden.add(Integer.toString(i));
		}

		visited = new boolean[10002];
		Queue<String> queue = new PriorityQueue<String>(10,
				new Comparator<String>() {
					// overriding the compare method
					public int compare(String i, String j) {
						if (i.compareTo(j) == 0)
							return 0;
						if (i.length() < j.length())
							return -1;
						if (i.length() == j.length() && i.compareTo(j) < 0)
							return -1;
						return 1;
					}
				});
		queue.add("");
		while (queue.isEmpty() == false) {
			String top = queue.poll();
			String tmp;
			for (int i = 0; i < nonForbidden.size(); i++) {
				tmp = top + nonForbidden.get(i);
				if (tmp.startsWith("0"))
					continue;
				int number = compose(tmp, N);
				if (visited[number])
					continue;
				if (number == 0) {
					return getReturn(tmp);
				}
				queue.add(tmp);
				visited[number] = true;
			}
		}
		return "IMPOSSIBLE";
	}

	public String getReturn(String s) {
		if (s.length() < 9)
			return s;
		else
			return s.substring(0, 3) + "..." + s.substring(s.length() - 3)
					+ "(" + s.length() + " digits)";
	}

	public int compose(String s, int N) {
		int sum = 0;
		for (int i = 0; i < s.length(); i++) {
			sum = sum * 10 + s.charAt(i) - '0';
			sum %= N;
		}
		return sum;
	}

	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
